{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lexicographical Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #字典树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lexicalOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字典序排数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，按字典序返回范围 <code>[1, n]</code> 内所有整数。</p>\n",
    "\n",
    "<p>你必须设计一个时间复杂度为 <code>O(n)</code> 且使用 <code>O(1)</code> 额外空间的算法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 13\n",
    "<strong>输出：</strong>[1,10,11,12,13,2,3,4,5,6,7,8,9]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lexicographical-numbers](https://leetcode.cn/problems/lexicographical-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lexicographical-numbers](https://leetcode.cn/problems/lexicographical-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['13', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        \n",
    "        strings = list(map(str,range(1,n+1)))\n",
    "        strings.sort()\n",
    "        \n",
    "        return list(map(int,strings))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        for i in range(1,n+1):\n",
    "            res.append(str(i))\n",
    "        res.sort()\n",
    "        for i in range(len(res)):\n",
    "            res[i]=int(res[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        returnList = []\n",
    "        for i in range(1,n+1):\n",
    "            returnList.append(str(i))\n",
    "        \n",
    "        returnList.sort()\n",
    "        for j in range(len(returnList)):\n",
    "            returnList[j] = int(returnList[j])\n",
    "            \n",
    "        return returnList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        self.n = n\n",
    "        heap = []\n",
    "        heapq.heapify(heap)\n",
    "        for i in range(1, n+1):\n",
    "            heapq.heappush(heap, str(i))\n",
    "        res = []\n",
    "        for i in range(1, n+1):\n",
    "            res.append(int(heapq.heappop(heap)))\n",
    "        \n",
    "        return res\n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def go(self, n, i, r):\n",
    "        \"\"\"\n",
    "        :type i: int\n",
    "        :type p: int\n",
    "        :type r: List[int]\n",
    "        \"\"\"\n",
    "        i *= 10\n",
    "        for j in range(10):\n",
    "            i2 = i + j\n",
    "            if i2 > n:\n",
    "                break\n",
    "            r.append(i2)\n",
    "            self.go(n, i2, r)\n",
    "\n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        r = []\n",
    "        for i in range(1, 10):\n",
    "            if i > n:\n",
    "                break\n",
    "            r.append(i)\n",
    "            self.go(n, i, r)\n",
    "        # print(r)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    x = []\n",
    "    def getS(self,root,n):\n",
    "        if root<=n:\n",
    "            self.x.append(root)\n",
    "            m = root*10\n",
    "            for i in range(10):\n",
    "                self.getS(m+i,n)\n",
    "                \n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        self.x=[]\n",
    "        for i in range(1,10):\n",
    "            self.getS(i,n)\n",
    "        return self.x\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 投机取巧，用字符串\n",
    "        # return [int(i) for i in sorted([str(i) for i in range(1, n+1, 1)])]\n",
    "\n",
    "        # 这种方法比较好\n",
    "        ret = [0] * n\n",
    "        num = 1\n",
    "        for i in range(n):\n",
    "            ret[i] = num\n",
    "            # 计算下一个位置的num\n",
    "            if num * 10 <= n:\n",
    "                num *= 10\n",
    "            else:\n",
    "                while num % 10 == 9 or num == n:\n",
    "                    num = num // 10\n",
    "                num += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        def dfs(cur,n,res):\n",
    "            if cur>n:\n",
    "                return\n",
    "            else:\n",
    "                res.append(cur)\n",
    "                for i in range(10):\n",
    "                    if 10*cur + i > n:\n",
    "                        return\n",
    "                    dfs(10*cur+i,n,res)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(1,10):\n",
    "            dfs(i,n,res)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ls = []\n",
    "        ln = []\n",
    "        for i in range(1,n+1):\n",
    "            s = str(i)\n",
    "            ls.append(s)\n",
    "        ls.sort()\n",
    "        for j in ls:\n",
    "            ln.append(int(j))\n",
    "        return ln\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1,10):\n",
    "            self.dfs(i,n,res)\n",
    "        return res\n",
    "        \n",
    "    def dfs(self,i,n,res):\n",
    "        if i>n:\n",
    "            return \n",
    "        res.append(i)\n",
    "        i *= 10\n",
    "        for j in range(10):\n",
    "            self.dfs(i+j,n,res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10):\n",
    "            self.dfs(i, n, res)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, i, n, res):\n",
    "        if i > n:\n",
    "            return\n",
    "\n",
    "        res.append(i)\n",
    "        for j in range(10):\n",
    "            self.dfs(i * 10 + j, n, res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res = [str(i) for i in range(1,n+1)]\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    nums = []\n",
    "    def ts(self, m, n):\n",
    "        for i in range(0, 10):\n",
    "            \n",
    "            if m + i <= n:\n",
    "                if i == 9 and m == 1:\n",
    "                    return\n",
    "                self.nums.append(m + i)\n",
    "                self.ts((m + i) * 10, n)\n",
    "            else:\n",
    "                return\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        self.nums.clear()\n",
    "        if n < 10:\n",
    "            for i in range(1, n + 1):\n",
    "                self.nums.append(i)\n",
    "        else:\n",
    "            self.ts(1, n)\n",
    "            #self.nums.pop()\n",
    "        return self.nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n):\n",
    "        ans = [0] * n\n",
    "        num = 1\n",
    "        for i in range(n):\n",
    "            ans[i] = num\n",
    "            if num * 10 <= n:\n",
    "                num *= 10\n",
    "            else:\n",
    "                while num % 10 == 9 or num + 1 > n:\n",
    "                    num //= 10\n",
    "                num += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        def dfs(nums:List[int], n:int, limit:int):\n",
    "            for i in range(0, 10):\n",
    "                if n == 0 and i == 0:\n",
    "                    continue\n",
    "                new = n * 10 + i\n",
    "                if new <= limit:\n",
    "                    # print(new)\n",
    "                    nums.append(new)\n",
    "                    dfs(nums, new, limit)\n",
    "            return nums\n",
    "        res = dfs([0], 0, n)\n",
    "        res.pop(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        x = 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(x)\n",
    "            if x*10 <= n:\n",
    "                x *= 10\n",
    "            else:\n",
    "                if x + 1 <= n and x % 10 != 9:\n",
    "                    x += 1\n",
    "                else:\n",
    "                    x //= 10\n",
    "                    while x % 10 == 9:\n",
    "                        x //= 10\n",
    "                    x += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        cur = 1\n",
    "\n",
    "        for _ in range(n):\n",
    "            res.append(cur)\n",
    "\n",
    "            if cur * 10 <= n:\n",
    "                cur *= 10\n",
    "            else:\n",
    "                while cur % 10 == 9 or cur + 1 > n:\n",
    "                    cur //= 10\n",
    "                \n",
    "                cur += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        num = 1\n",
    "        for i in range(n):\n",
    "            ans[i] = num\n",
    "            if num * 10 <= n:\n",
    "                num *= 10\n",
    "            else:\n",
    "                while num % 10 == 9 or num + 1 > n:\n",
    "                    num //= 10\n",
    "                num += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        def dfs(x):\n",
    "            yield x\n",
    "            for nxt in range(x * 10, min(n + 1, (x + 1) * 10)):\n",
    "                yield from dfs(nxt)\n",
    "        return [v for i in range(1, min(n + 1, 10)) for v in dfs(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        if not n:\n",
    "            return []\n",
    "        res = [1]*n\n",
    "        num = 1\n",
    "        for i in range(1,n):\n",
    "            if num * 10 <= n:\n",
    "                num *= 10\n",
    "            else:\n",
    "                while num%10 == 9 or num+1>n:\n",
    "                    num = num // 10\n",
    "                num += 1\n",
    "            res[i] = num\n",
    "        return res \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        def recur(cur):\n",
    "            result=[cur]\n",
    "            for i in range(10):\n",
    "                c=cur*10+i\n",
    "                if c==0:\n",
    "                    continue\n",
    "                if c>n:\n",
    "                    return result\n",
    "                result+=recur(c)\n",
    "            return result\n",
    "            \n",
    "        return recur(0)[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "\n",
    "        res = [_ for _ in range(1, min(10,n+1))]\n",
    "        num = 10\n",
    "        while num <= n:\n",
    "            breakpoint = res.index(num//10)+1\n",
    "            res = res[:breakpoint] + [_ for _ in range(num, min(num+10,n+1))] + res[breakpoint:]\n",
    "            num += 10\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        def compare(a, b):\n",
    "            if str(a) < str(b):\n",
    "                return -1\n",
    "            elif str(a) > str(b):\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        res = list(range(1, n + 1))\n",
    "        res.sort(key=functools.cmp_to_key(compare))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        r = []\n",
    "        def dfs(st):\n",
    "            if st <= n:\n",
    "                r.append(st)\n",
    "            else:\n",
    "                return\n",
    "            for i in range(10):\n",
    "                x = st*10+i\n",
    "                if x > n:\n",
    "                    break\n",
    "                dfs(x)\n",
    "        for i in range(1,10):\n",
    "            dfs(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "        def dfs(cur: int) -> None:\n",
    "            i = 0\n",
    "            if cur == 0: i = 1\n",
    "            else: res.append(cur)\n",
    "            if cur == n: return \n",
    "            while i < 10: \n",
    "                if cur * 10 + i > n: break\n",
    "                dfs(cur * 10 + i)\n",
    "                i += 1\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i>n:\n",
    "                return \n",
    "            \n",
    "            res.append(i)\n",
    "            for j in range(10):\n",
    "                dfs(i*10+j)\n",
    "        \n",
    "        for i in range(1,10):\n",
    "            dfs(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        r=Result(n+1)\n",
    "\n",
    "        def recur(val):\n",
    "            if val>n:\n",
    "                return\n",
    "            r.add(val)\n",
    "            if val*10>n:\n",
    "                return\n",
    "            for i in range(10):\n",
    "                c=val*10+i\n",
    "                if c==0:\n",
    "                    continue\n",
    "                recur(c)\n",
    "\n",
    "        recur(0)\n",
    "        return r.result[1:]\n",
    "\n",
    "class Result:\n",
    "    def __init__(self,n):\n",
    "        self.result=[0]*n\n",
    "        self.cur_index=0\n",
    "    \n",
    "    def add(self,val):\n",
    "        self.result[self.cur_index]=val\n",
    "        self.cur_index+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        return [int(i) for i in sorted((str(i) for i in range(1, n + 1)))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        return sorted(range(1, n+1), key=str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        res=[]\n",
    "        while n>0:\n",
    "            res.append(n)\n",
    "            n-=1\n",
    "        rs=sorted(res,key=str)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicalOrder(self, n: int) -> List[int]:\n",
    "        arr = [str(i) for i in range(1,n+1)]\n",
    "        arr.sort()\n",
    "        final = [int(i) for i in arr]\n",
    "        return final"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
